package com.leetcode.二叉树;

import com.leetcode.二叉树.L104二叉树的最大深度.TreeNode;

/**
 * 给定一个二叉树，找出其最小深度。
 * 
 * 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
 * 
 * 说明：叶子节点是指没有子节点的节点。
 * 
 * 虽然题意说的是节点数量，但本质还是深度，只不过是求最小的那个深度
 * 本题可以使用深搜，也可以使用层次遍历
 * 使用层次遍历，当遍历到第一个叶子节点，就可以返回了。
 * 本题以深度优先搜索为例：
 * 
 * @author LZF
 *
 */
public class L111二叉树的最小深度 {
	public int minDepth(TreeNode root) {
		return dfs(root);
	}
	public int dfs(TreeNode node) {
		if(node == null) return 0;
		else {
			int cntLeft = dfs(node.left);
			int cntRight = dfs(node.right);
			//如果左右子树有一个深度为0，则总的深度应该是根节点root加上另外一个子树的深度
			if(cntLeft == 0 || cntRight == 0) {
				return 1 + cntLeft + cntRight;
			} else {//如果都不为0，则取左右子树最小的
				return 1 + Math.min(cntLeft,cntRight);
			}
		}
	}
	// 树的定义
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode() {
		}

		TreeNode(int val) {
			this.val = val;
		}

		TreeNode(int val, TreeNode left, TreeNode right) {
			this.val = val;
			this.left = left;
			this.right = right;
		}
	}
}
